CF17E Palisection

答案为所有的回文串组合-不相交的回文串组合。

cntcnt 为回文串个数 , 可以通过计算每个节点的回文串数量求得。

不相交的回文组合也比较好求,先算出以 ii 为左端点和右端点的回文串数量 L[i]L[i] , R[i]R[i]

阅读全文 »

UVA1218 Perfect Service

一道很不错的树形dp。

dp[u][f]dp[u][f] 为以uu为根的子树。

f=0f=0,表示uu为服务器,那么uu的儿子和父亲既可以是服务器,也可以不是。

阅读全文 »

CF767C Garland

首先可以确定的是,如果点权和不为3的倍数,一定不存在合法方案。

记所有点权和为sumsum

容易想到,令 dp[u]dp[u] 表示以 uu 为根的子树的点权和 , 则有转移:

阅读全文 »

SP9934 ALICE - Alice and Bob

这道题的状态挺难设计的。。。

ss 为石子的总数,那么操作次数最多为 s+(n1)s+(n-1)

如果石子数量全不为一,那么先手必胜的条件为 s+(n1)s+(n-1) 为奇数,因为他一定可以保证操作 s+(n1)s+(n-1) 次。

阅读全文 »

UVA1500 Alice and Bob

这道题的状态挺难设计的。。。

ss 为石子的总数,那么操作次数最多为 s+(n1)s+(n-1)

如果石子数量全不为一,那么先手必胜的条件为 s+(n1)s+(n-1) 为奇数,因为他一定可以保证操作 s+(n1)s+(n-1) 次。

阅读全文 »

P4056 [JSOI2009]火星藏宝图

首先有一个非常 naive 的 O(n2)\mathcal{O(n^2)} dp。

dpidp_i 表示到第 ii 座岛的最大收益,那么有:

dpi=max1jn,j=i,xjxi,yjyi{dpj(xixj)2(yiyj)2}+vidp_i=\max_{1\le j \le n, j \not= i ,x_j \le x_i ,y_j \le y_i }\{dp_j-(x_i-x_j)^2-(y_i-y_j)^2\}+v_i

阅读全文 »